1. Field
The present disclosure is directed to image processing and, in particular, to a method for inpainting of images. Those images can be color or greyscale images. In particular, by way of example and not of limitation, the greyscale images can be binary images. A binary image is one with only two different intensities or hues. A black and white image is binary, for example an image made up of printed text. On the other hand, a greyscale image has all grey values between black and white, such as what one might obtain from a photograph of a scene.
2. Related Art
Image inpainting is the filling in of damaged or missing regions of an image with the use of information from surrounding areas. In its essence, it is a type of interpolation. Its applications include restoration of old paintings by museum artists, and removing scratches from photographs.
The pioneering work of Bertalmio, et al. [M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, “Image inpainting,” in Siggraph 2000, Computer Graphics Proceedings, K. Akeley, Ed. ACM Press/ACM SIGGRAPH/Addison Wesley Longman 2000, pp. 417-424] introduced image inpainting for digital image processing. Their model is based on nonlinear partial differential equations, and imitates the techniques of museum artists who specialize in restoration. They focuse on the principle that good inpainting algorithms should propagate sharp edges into the damaged parts that need to be filled in. This can be done, for instance, by connecting contours of constant greyscale image intensity (called isophotes) to each other across the inpainting region (see also S. Masnou and J. Morel, “Level lines based disocclusion” 5th IEEE Int'l Conf. on Image Processing, Chicago, Ill. Oct. 4-7, 1998), so that gray levels at the edge of the damaged region extend continuously into the interior. They also impose the direction of the isophotes as a boundary condition at the edge of the inpainting domain.
In subsequent work with Bertozzi [M. Bertalmio, A. Bertozzi, and G. Sapiro, “Navier-Stokes, fluid dynamics, and image and video inpainting.” IEEE Computer Vision and Pattern Recognition (CVPR), Hawaii, vol.1, pp. 1355-1362, Dec. 2001], they realized that the method in Bertalmio, et al. has intimate connections with two dimensional fluid dynamics through the Navier-Stokes equation. Indeed, the steady state equation proposed in Bertalmio, et al. is equivalent to the inviscid Euler equations from incompressible flow, in which the image intensity function plays the role of the stream function in the fluid problem.
The natural boundary conditions for inpainting are to match the image intensity on the boundary of the inpainting region, and also the direction of the isophote lines (∇⊥I). For the fluid problem this is effectively a generalized ‘no-slip’ boundary condition that requires a Navier-Stokes formulation, introducing a diffusion term. This analogy also shows why diffusion is required in the original inpainting problem. In practice nonlinear diffusion (P. Perona and J. Malik, “Scale-space and edge detection using anisotropic diffusion,” IEEE Trans. Patern Anal Machine Intell. vol. 12, pp. 629-639, 1990; L. Rudin, S. Osher, and E. Fatemi, “Non linear total variation based noise removal algorithms,” Physica D, vol. 60, pp. 259-268, 1992) works very well to avoid blurring of edges in the inpainting.
A different approach to inpainting was proposed by Chan and Shen [T.F. Chan and J. Shen, “Mathematical models of local non-texture inpaintings,” SLAM Journal on Applied Mathematics, vol. 62, no. 3, pp.1019-1043, 2001]. They introduced the idea that well-known variational image denoising and segmentation models can be adapted to the inpainting task by a simple modification. These models often include a fidelity term that keeps the solutions close to the given image. By restricting the effects of the fidelity term to the complement of the inpainting region, Chan and Shen showed that very good image completions can be obtained. The principle behind their approach can be summarized as follows: variational denoising and segmentation models all have an underlying notion of what constitutes an image. In the inpainting region, the models of Chan and Shen reconstruct the missing image features by relying on this built-in notion of what constitutes a natural image.
The first model introduced by Chan and Shen used the total variation based image denoising model of Rudin, Osher, and Fatemi mentioned above. This model can successfully propagate sharp edges into the damaged domain.
However, because of a regularization term, the model exacts a penalty on the length of edges, and thus the inpainting model cannot connect contours across very large distances. Another caveat is that this model does not continuously extend the direction of isophotes across the boundary of the inpainting domain.
Subsequently, Chan, Kang, and Shen [T. Chan, S. Kang and J. Shen, “Euler's elastica and curvature-based inpaintings,” SLAM Journal on Applied Mathematics, vol. 63, no.2. pp. 564-592, 2002] introduced a new variational image inpainting model that addressed the caveats of the total variation based one. Their model is motivated by the work of Nitzberg, Mumford, and Shiota, [M. Nitzberg, D. Mumford, and T. Shiota, Filtering, Segmentation, and Depth, ser. Lecture Notes in Computer Science. Springer-Verlag, 1993, no. 662] and includes a new regularization term that penalizes not merely the length of edges in an image, but the integral of the square of curvature along the edge contours. This allows both for isophotes to be connected across large distances, and their directions to be kept continuous across the edge of the inpainting region.
Following in the footsteps of Chan and Shen, Esedoglu and Shen [S. Esedoglu and J. Shen, “Digital impainting based on the Munford-Shah-Euler image model,” European Journal of Applied Mathematics, vol. 13, pp. 353-370, 2002] adapted the Mumford-Shah image segmentation model [D. Mumford and J. Shah, “Optimal approximations by piecewise smooth functions and associated with variational problems,” Communications on Pure and Applied Mathematics, vol. 42, pp. 577-685, 1989] to the inpainting problem for greyscale images. They utilized Ambrosio and Tortorelli's elliptic approximations [L. Ambrosio and V. M. Tortorelli, “Approximation of functionals depending on jumps by elliptic functionals via gamma convergence,” Communications on Pure and Applied Mathematics, vol. 43, pp. 999-1036, 1990] to the Mumford-Shah functional. Gradient descent for these approximations leads to parabolic equations with a small parameter ε in them; they represent edges in the image by transition regions of thickness ε. These equations have the benefit that highest order derivatives are linear. They can therefore be solved rather quickly. However, like the total variation image denoising model, the Mumford-Shah segmentation model penalizes length of edge contours, and as a result does not allow for the connection of isophotes across large distances in inpainting applications.
In order to improve the utility of the Mumford-Shah model in inpainting, Esedoglu and Shen introduced the Mumford-Shah-Euler image model that, just like the previous work of Kang, Chan, and Shen mentioned above, penalizes the square of the curvature along an edge contour. Following previous work by March [R. March and M. Dozio, “A variational method for the recovery of smooth boundaries,” Image and Vision Computing, vol. 15, no. 9, pp. 705-712, 1997], they then used a conjecture of De Giorgi [E. De Giorgi, “Some remarks on gamma-convergence and least squares methods,” in Composite Media and Homogenization Theory, G. D. Maso and G. F. Dell'Antonio, Eds. Birkhauser, 1991, pp. 135-142] to approximate the resulting variational problem by an elliptic one. The resulting gradient descent equations are fourth order, nonlinear parabolic PDE (partial differential equation) with a small parameter in them.
More recently, Grossauer and Scherzer [H. Grossauer and O. Scherzer, “Using the complex Ginzburg-Landau equation for digital inpainting in 2d and 3d”, Scale Space Methods in Computer Vision, Lecture Notes in Computer Science 2695, pp. 225-236, 2003] have used the complex Ginzburg-Landau equation in a technique for inpainting greyscale images. This method assigns the real part u of a complex quantity w=u+iv to be the greyscale values of the image. The complex quantity w is then forced by their algorithm to reside on a circle of radius 1, centered at the origin, in the complex plane. The complex Ginzburg-Landau equation then leads to a coupled system to be solved for u and v, respectively.
All of the above methods are PDE-based methods. With regard to other kinds of methods for binary inpainting, the closest in spirit are those based on spline continuation of the edges [G. Schuster, X. Li, and A. K. Katsaggelos, “Spline-based boundary loss concealment,” Proceedings of the IEEE International Conference on Image Processing, 2003; L. D. Soares and F. Pereira, “Spatial shape error concealment for object-based image and video coding,” IEEE Trans. Image Proc. vol. 13, no. 4, 2004]. This approach is very fast for simple regions and the complexity of the algorithm depends on the number of edges involved in the inpainting problem.